1. Field of the Invention
The disclosures herein generally relate to methods of allocating functions to memory space, and particularly relate to a cache coloring method that allocates functions to memory space such as to reduce the possibility of cache conflict.
2. Description of the Related Art
In computer systems, generally, a cache memory that is smaller in capacity and faster than the main memory is provided in addition to the main memory. Part of the information stored in the main memory is copied to the cache. When this information needs to be accessed, a faster retrieval of information is attained by reading the information from the cache rather than from the main memory.
As caches are capable of high-speed operations and thus more expensive than main memories, their storage capacity is very small. A cache contains a plurality of cache lines, and the copying of information from an external memory (i.e., the main memory) to the cache is performed on a cache-line-specific basis. Because of this, the memory space of the external memory is divided in units of cache lines, and the divided memory areas are successively allocated to the cache lines in advance. Since the capacity of the cache is smaller than the capacity of the external memory, the memory areas of the external memory are repeatedly allocated to the same cache lines.
When program functions are to be executed, different program functions allocated to different addresses in the external memory may be allocated to the same cache line. In this case, one of the program functions needs to be copied to the cache at every turn when the program functions are alternately called. This is referred to as cache conflict. The problem is that the more frequent the occurrence of cache conflict, the slower the execution speed of the program is. In order to obviate this problem, it is preferable to avoid allocating functions having the high likelihood of simultaneous executions to the same cache line, and research efforts have been made to this end.
In order to obviate the problem of cache conflict, the strength of function may be defined as an indication of the number of calls between functions and the number of calls of a specific function-calling pattern. In the related art, there is a method by which functions having the great strength of function (i.e., there is a high possibility of the functions calling each other) are not allocated to the same cache line. Setting and modifying of link sequences on a function-specific basis for the purpose of reducing cache conflict and instruction cache miss is called cache coloring.
In the cache coloring method (see Patent Document 1) proposed by the applicant of this application, function strength information is generated in response to a dynamic function flow representing a time sequence in which a plurality of functions are called at the time of program execution, such that the function strength information includes information about runtime relationships between all the functions in terms of a way the functions are called. The dynamic function flow may be generated by tracing the calling of functions at the time of program execution. The function strength information can represent mutual relationships between functions (relationships between any given function and all the other functions), which was impossible in the conventional art. The use of such information makes it possible to provide the optimum allocation of functions that minimizes the number of instruction cache misses. The cache coloring method disclosed in Patent Document 1 provides four different types of function strength information as specific definitions of function strength information.
In general, the effect of cache miss suppression may depend on individual programs when a specific type of function strength information is used for cache coloring. Namely, the effect of cache miss suppression may be sufficient with respect to a given program while the effect of cache miss suppression may not be sufficient with respect to other programs. In this case, the definition of function strength information used may not have been properly designed for general use. Accordingly, there is a need for a definition of function strength information that can universally reduce cache misses regardless of differences in individual programs.
Accordingly, there is a need for a cache coloring method based on such definition of function strength information that cache misses can be universally reduced regardless of differences in individual programs.
[Patent Document 1] Japanese Patent Application Publication No. 2005-266941
[Patent Document 2] Japanese Patent Application Publication No. 2003-271394